﻿#define _CRT_SECURE_NO_WARNINGS 1

// https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/

#include <iostream>
using namespace std;

#include <assert.h>

struct TreeNode 
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution
{
public:
    // 查找x是否在树中
    bool IsInTree(TreeNode* root, TreeNode* x)
    {
        if (root == nullptr)
            return false;
        return root == x || IsInTree(root->left, x) || IsInTree(root->right, x);
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
    {
        if (root == nullptr)
            return nullptr;
        if (root == p || root == q) {

            return root;
        }

        // 这⾥要注意，这⾥的命名⾮常关键，命名好了，代码可读性⼤⼤增强
        bool pInLeft, pInRight, qInLeft, qInRight;

        // 题⽬中有说明p和q⼀定是树中的结点
        // p不在左树就在右树
        pInLeft = IsInTree(root->left, p);
        pInRight = !pInLeft;

        // q不在左树就在右树
        qInLeft = IsInTree(root->left, q);
        qInRight = !qInLeft;

        // ⼀个在左，⼀个在右，那么root就是最近公共祖先
        // 都在左，递归去左树查找
        // 都在右，递归去右树查找
        if ((pInLeft && qInRight) || (qInLeft && pInRight))
        {
            return root;
        }
        else if (pInLeft && qInLeft)
        {
            return lowestCommonAncestor(root->left, p, q);
        }
        else if (pInRight && qInRight)
        {
            return lowestCommonAncestor(root->right, p, q);
        }

        assert(false);
        return NULL;

    }
};

int main()
{
    // root = [3,5,1,6,2,0,8,null,null,7,4]
    TreeNode* root = new TreeNode(3);

    root->left = new TreeNode(5);
    root->right = new TreeNode(1);

    root->left->left = new TreeNode(6);
    root->left->right = new TreeNode(2);
    root->right->left = new TreeNode(0);
    root->right->right = new TreeNode(8);

    root->left->right->left = new TreeNode(7);
    root->left->right->left = new TreeNode(4);

    auto p = root->left, q = root->right;

    cout << root << endl;
    cout << Solution().lowestCommonAncestor(root, p, q) << endl;

    return 0;
}



